package leetcode.lcp.lcp20230422;

//Solution1Test
public class Solution1 {

	public int[] supplyWagon(int[] supplies) {
		int n = supplies.length;
		int m = n / 2;

		return f(supplies, m);
	}

	private int[] f(int[] supplies, int m) {
		if (supplies.length == m) {
			return supplies;
		}
		int[] ans = new int[supplies.length - 1];
		int min = Integer.MAX_VALUE, idx = -1;
		for (int i = 1; i < supplies.length; i++) {
			int cur = supplies[i] + supplies[i - 1];
			if (cur < min) {
				min = cur;
				idx = i - 1;
			}
		}
		for (int i = 0, j = 0; i < supplies.length; i++, j++) {
			if (i != idx) {
				ans[j] = supplies[i];
			} else {
				ans[j] = supplies[i] + supplies[i + 1];
				i++;
			}
		}
		return f(ans, m);
	}

}
